package org.review.algorithm.sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/**
 * 希尔排序是希尔（Donald Shell）于 1959 年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，
 * 也称为缩小增量排序。
 * 希尔排序的思想： 将无序数组按照步长 进行分组，先对小组进行排序， 之后再对相对有序的数组分组，直到/2等于1,此时最后一次再排序就简单很多并得出结果 （1再除2就等于0了）
 * step 1： 计算步长  gap =  length/2
 * step 2:  i步长起始位置开始遍历整个数组
 * step 3： j=起始位置i-步长 就是开始元素位置（因为起始位置i就是步长的截取初始，他减去步长就是0）
 * step 4:  此时会有两种实现 1：j代表后元素;j-步长gap 代表组内要比较的前元素， 判断退出就是j>gap
 * 2：j代表前元素;j+gap 代表组内要比较的后元素,此时退出循环条件就是j>=0;
 * step 5:  根据step4的1 和2意义， 实现也会有两个
 */
public class ShellSort {

    public static void main(String[] args) {
    /*    int[] arr = {12, 34, 54, 2, 3, 5, 9, 8, 1};
        Arrays.stream(arr).mapToObj(e -> e + " ").forEach(System.out::print);
        //moveSort(arr);
        changeSort(arr);
        System.out.println("排序后的数组:");
        Arrays.stream(arr).mapToObj(e -> e + " ").forEach(System.out::print);*/


        int[] arr = new int[9000000];
        for (int i = 0; i < 9000000; i++) {
            arr[i] = (int) (Math.random() * 9000000); // 生成一个[0, 8000000) 数
        }
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String date1Str = simpleDateFormat.format(new Date());
        System.out.println("排序前的时间是=" + date1Str);
        moveSort(arr);
       // changeSort(arr);
        String date2Str = simpleDateFormat.format(new Date());
        System.out.println("排序后的时间是=" + date2Str);
        //Arrays.stream(arr).mapToObj(e -> e + " ").forEach(System.out::print);
    }

    /**
     * 移位方式实现
     */
    private static void moveSort(int[] arr) {

        int j, var;
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                j = i;
                var = arr[i];

                while (j >= gap && arr[j - gap] > var) {
                    arr[j] = arr[j - gap];
                    j -= gap;
                }
                arr[j] = var;
            }
        }
    }

    /**
     * 交换方式实现
     */
    private static void changeSort(int[] arr) {
        int length = arr.length;
        for (int gap = length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < length; i++) {
                for (int j = i - gap; j >= 0; j -= gap) {
                    if (arr[j] > arr[j + gap]) {//TODO 2024/8/28:如果前边大于后边就交换位置
                        int temp = arr[j];
                        arr[j] = arr[j + gap];
                        arr[j + gap] = temp;
                    }
                }
            }
        }
    }
}
